`
https://leetcode.cn/problems/4sum/
`

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  // 数组排序
  nums.sort((a, b) => a - b)
  const res = []

  for (let i = 0; i < nums.length; i++) {
    // 对 target - nums[i] 计算 threeSum
    const tuple = threeSum(nums, i + 1, target - nums[i])
    // 如果存在满足条件的三元组，再加上 nums[i] 就是结果四元组
    for (let j = 0; j < tuple.length; j++) {
      tuple[j].push(nums[i])
      res.push(tuple[j])
    }

    // 跳过与当前数字重复的情况，否则会出现重复结果
    while (i < nums.length - 1 && nums[i] === nums[i + 1]) i++
  }

  return res
};

// 计算在 nums[start...num.length-1] 中结果为 target 的三个数的所有组合
function threeSum(nums, start, target) {
  const res = []

  for (let i = start; i < nums.length; i++) {
    // 对 target - nums[i] 计算 twoSum
    const tuple = twoSumTarget(nums, i + 1, target - nums[i])
    // 如果存在满足条件的二元组，再加上 nums[i] 就是结果三元组
    for (let j = 0; j < tuple.length; j++) {
      tuple[j].push(nums[i])
      res.push(tuple[j])
    }

    // 跳过与当前数字重复的情况，否则会出现重复结果
    while (i < nums.length - 1 && nums[i] === nums[i + 1]) i++
  }

  return res
};

// 计算在 nums[start...num.length-1] 中结果为 target 的两个数的所有组合
function twoSumTarget(nums, start, target) {
  let lo = start, hi = nums.length - 1;
  const res = [];
  while (lo < hi) {
    let sum = nums[lo] + nums[hi];
    let left = nums[lo], right = nums[hi];
    if (sum < target) {
      // 跳过重复的元素
      while (lo < hi && nums[lo] == left) lo++;
    } else if (sum > target) {
      // 跳过重复的元素
      while (lo < hi && nums[hi] == right) hi--;
      // 缩小窗口
    } else {
      res.push([left, right]);
      // 跳过重复的元素 
      while (lo < hi && nums[lo] == left) lo++;
      while (lo < hi && nums[hi] == right) hi--;
    }
  }
  return res;
};